//
//  16__部分排序.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/8.
/**
 给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

 示例：

 输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
 输出： [3,9]

 */

import UIKit

class BuFenSort: NSObject {
    func QA() {
        let array = [1,2,4,7,10,11,7,12,6,7,16,18,19];
        print(subSort(array))
    }
    
    func subSort(_ array: [Int]) -> [Int] {
        if array.count == 0 {
            return [-1, -1]
        }
        // 从左到右找逆序对
        var left = -1
        var maxNum = array[0]
        var i = 1
        while i < array.count {
            if array[i] >= maxNum {
                maxNum = array[i]
            } else {
                left = i
            }
            i += 1
        }
        // 从右向左找逆序对
        var right = -1
        var minNum = array[array.count - 1]
        var j = array.count - 2
        while j >= 0 {
            if array[j] <= minNum {
                minNum = array[j]
            } else {
                right = j
            }
            j -= 1
        }
        
        return [right, left]
    }
}
